package com.java.recursive;

/**
 * 使用递归解决八皇后问题（92种解法）
 * 使用一维数组来保存问题的解 如 {0,4,7,5,2,6,1,3}
 * 第几个数就代表这个棋子在行， 它的值就代表它在第几列
 * @author 19252
 * @date 2020/7/13
 */
public class EightQueensProblem {

    private int max = 8;
    private int[] queens = new int[max];
    private int count = 0;

    public static void main(String[] args) {
        EightQueensProblem queensProblem = new EightQueensProblem();
        queensProblem.putQueen(0);
        System.out.println(queensProblem.count);
    }


    /**
     * 开始放置皇后
     * @param n 第几个皇后
     */
    public void putQueen(int n){
        // 如果n == max 证明已经得到了可行的解
        // 因为 是使用 一维数组来放置的 可以存储的数值最大为 max - 1
        if (n == max){
            showQueens();
            count ++;
        }else {
            // 如果还有放置皇后的空间，就继续放置
            // 并判断是否有冲突与已经放置了的
            for (int i = 0; i < max; i ++){
                // 首先将这个皇后放置在本行的第一个位置
                queens[n] = i;
                // 冲突判断
                if (judge(n)){
                    // 没有冲突，再放置下一个皇后
                    putQueen(n + 1);
                }
                // 如果有冲突，就继续执行 queens[n] = i;
                // 即将第n个皇后，放置在本行的后移一个位置
            }
        }
    }


    /**
     * 对当前皇后的位置的合法性进行校验
     * @param n 表示第几个皇后
     * @return 返回是否与前面的皇后有冲突 false 表示有，true表示没有
     */
    public boolean judge(int n){
        for (int i = 0; i < n; i++) {
            // queen[i] == queen[n] 相等表示在同一列，位置冲突
            // Math.abs(n - i) == Math.abs(queen[n] - queen[i]) 相等在同一斜线上
            // 同一斜线上的两点，横坐标相减的绝对值等于纵坐标相减的绝对值
            // Math.abs(n - i) 横坐标  Math.abs(queen[n] - queen[i])纵坐标
            if (queens[i] == queens[n] || Math.abs(n - i) == Math.abs(queens[n] - queens[i])){
                return false;
            }
        }
        return true;
    }


    /**
     * 打印输出皇后所在的位置，及解法
     */
    public void showQueens(){
        for (int i : queens){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
